/*
 *https://leetcode.cn/problems/insufficient-nodes-in-root-to-leaf-paths/
 *1080. 根到叶路径上的不足节点
 *medium 吴朝泽 2024.11.12
 *DFS深度优先搜索
*/

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* sufficientSubset(TreeNode* root, int limit) {
        // 如果当前节点为空，直接返回 nullptr
        if (!root) {
            return nullptr;
        }
        
        // 从当前节点的值中扣除 limit，作为新的限制
        limit -= root->val;

        // 如果当前节点是叶子节点（没有左子树和右子树）
        if (!root->left && !root->right) {
            // 如果当前节点的值累加后超过了 limit，返回 nullptr（意味着这个叶子节点不符合条件）
            // 如果累加后的值没有超过 limit，说明这个叶子节点满足条件，返回该节点
            return limit > 0 ? nullptr : root;
        }

        // 递归处理左子树，如果左子树不满足条件，返回 nullptr
        root->left = sufficientSubset(root->left, limit);

        // 递归处理右子树，如果右子树不满足条件，返回 nullptr
        root->right = sufficientSubset(root->right, limit);

        // 如果当前节点的左子树和右子树都为 nullptr（说明它的两个子树都没有满足条件的子节点）
        // 则当前节点也不满足条件，返回 nullptr
        return !root->left && !root->right ? nullptr : root;
    }
};
